package 排序链表;
//归并排序，时间复杂度nlogn,空间复杂度n
public class Solution1 {
    public ListNode sortList(ListNode head) {
        if(head==null || head.next == null){
            return head;
        }
        ListNode slow = new ListNode();
        slow = head;
        ListNode fast = new ListNode();
        fast = head.next;
        while(head != null && head.next!=null){
            slow = slow.next;
            fast = fast.next;
        }
        ListNode temp = new ListNode();
        temp = slow.next;
        slow.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(temp);

        ListNode h = new ListNode();
        ListNode res = h;


        while(left !=null && right!=null){
            if(left.val < right.val){
                h.next = left;
                left = left.next;
            }else {
                h.next =right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null? left:right;
        return res.next;
    }
}
